package com.zk.algorithm.string;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class ImplementStrStr {

    // Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
    public int strStr(String haystack, String needle) {
        if (haystack == null) {
            return -1;
        }

        if (needle == null || needle.isEmpty()) {
            return 0;
        }

        if (needle.length() > haystack.length()) {
            return -1;
        }

        int hayStackStart = 0;
        int needleStart = 0;

        while (hayStackStart <= haystack.length() - 1) {

            if (haystack.charAt(hayStackStart) == needle.charAt(needleStart)) {
                int ans = hayStackStart;
                int i = hayStackStart;
                int j = needleStart;
                int matched = 0;

                while (i < haystack.length() &&
                        j < needle.length() &&
                        haystack.charAt(i++) == needle.charAt(j++)) {
                    matched++;
                }

                if (matched == needle.length()) {
                    return ans;
                }
            }

            hayStackStart++;

        }

        return -1;
    }

    public static void main(String...args) {
        ImplementStrStr implementStrStr = new ImplementStrStr();

        Utils.println(implementStrStr.strStr("mississippi", "issip"));
        Utils.println(implementStrStr.strStr("hello", "ll"));
        Utils.println(implementStrStr.strStr("aaaaa", "bba"));
        Utils.println(implementStrStr.strStr("abcdefg", "def"));
        Utils.println(implementStrStr.strStr("leetcode", "123"));
        Utils.println(implementStrStr.strStr("leetcode", ""));
        Utils.println(implementStrStr.strStr("", "xxxxx"));
    }

}